package com.lcm.oj.labuladong.p0;

import java.util.Arrays;
import java.util.TreeMap;

/**
 * @author Coder-lcm
 * @date 2021/4/5
 *      常见的基础数据结构无非就以下三种
 *         （1）数组： 定长、连续分配的内存空间、可随机访问，插入或删除元素需要移动一大堆的元素（时间复杂度为O（n）），查询因为是根据索引来查询，因此速度非常的快，复杂度为O（1）
 *         （2）链表： 不连续分配，每个元素都需要维持着下一个元素节点的指针，增删比较快（找到对应元素，修改指针指向即可），查询较慢（因为要遍历所有节点才能找到，而且也没有索引，时间复杂度为O(n)）
 *         （3）树
 *
 *
 */
public class DataStructure {
    public static void main(String[] args) {
        // 数组
        int[] ints = new int[8];
        Arrays.fill(ints, 8);
        for (int i : ints) {
            System.out.print(i+", ");
        }

        // 链表
        LinkNode linkNode = new LinkNode(12, new LinkNode(34, new LinkNode(32, new LinkNode(34))));
        // 1.通过迭代来遍历链表
        while (linkNode != null && linkNode != null) {
            System.out.print(linkNode.val);
            linkNode = linkNode.next;
            if (linkNode != null) {
                System.out.print("->");
            }
        }
        // 2.通过递归来遍历链表
        System.out.println("\n++++++++++递归遍历链表+++++++++");
        linkNode = new LinkNode(12, new LinkNode(34, new LinkNode(32, new LinkNode(34))));
        traverse(linkNode);

        // 二叉树
        TreeNode treeNode = new TreeNode(23, new TreeNode(34, new TreeNode(56), new TreeNode(89)), new TreeNode(45, new TreeNode(45), null));


    }

    // 递归遍历，这里以递归遍历链表为例
    public static void traverse(LinkNode node){
        System.out.print(node.val);
        if (node.next != null) {
            System.out.print("->");
            traverse(node.next);
        }
    }
}
class LinkNode{
    public Object val;
    public LinkNode next;

    public LinkNode(){}

    public LinkNode(Object val) {
        this.val = val;
        this.next = null;
    }

    public LinkNode(Object val, LinkNode next) {
        this.val = val;
        this.next = next;
    }

}
// 二叉树
class TreeNode{
    private int val;
    private TreeNode left;
    private TreeNode right;

    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    public TreeNode() {
    }

}